|
, and . Without further constraints, 3 *23=24 utility values would be required to describe such a game. |- | !align="center"|''L'', ''l'' !align="center"|''L'', ''r'' !align="center"|''R'', ''l'' !align="center"|''R'', ''r'' |- !align="center"|''T'' |align="center"|, , |align="center"|, , |align="center"|, , |align="center"|, , |- !align="center"|''B'' |align="center"|, , |align="center"|, , |align="center"|, , |align="center"|, , |- |colspan="5"|''For each strategy profile, the utility of the first player is listed first (), and is followed by the utilities of the second player () and the third player ().'' |} In algorithmic game theory, a succinct game or a succinctly representable game is a game which may be represented in a size much smaller than its normal form representation. Without placing constraints on player utilities, describing a game of players, each facing strategies, requires listing utility values. Even trivial algorithms are capable of finding a Nash equilibrium in a time polynomial in the length of such a large input. A succinct game is of ''polynomial type'' if in a game represented by a string of length ''n'' the number of players, as well as the number of strategies of each player, is bounded by a polynomial in ''n''〔 (a formal definition, describing succinct games as a computational problem, is given by Papadimitriou & Roughgarden 2008〔). ==Types of succinct games== 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Succinct game」の詳細全文を読む スポンサード リンク
|